//
// Created by 紫霄 on 2020/4/11.
//

#ifndef LEETCODE_13_H
#define LEETCODE_13_H
#include <vector>
using namespace std;
class Solution {
public:
  int movingCount(int m, int n, int k) {
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    int o;
    return o = dfs(0, 0, m, n, k, visited);
  }
  int dfs(int curRow, int curCol, int m, int n, int k,
          vector<vector<bool>> &visited) {
    if (curRow >= m || curCol >= n || digitSum(curCol) + digitSum(curRow) > k ||
        visited[curRow][curCol]) {
      return 0;
    } else {
      visited[curRow][curCol] = true;
      return 1 + dfs(1 + curRow, curCol, m, n, k, visited) +
             dfs(curRow, 1 + curCol, m, n, k, visited);
    }
  }
  int digitSum(int i) {
    int sum = 0;
    while (i != 0) {
      sum += i % 10;
      i /= 10;
    }
    return sum;
  }
};
#endif // LEETCODE_13_H
